Leetcode 312.戳气球

题目描述：

有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1 或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

示例 1：

1
2
3
4
5

输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

示例 2：

1
2

输入：nums = [1,5]
输出：10

提示：

• n == nums.length
• 1 <= n <= 500
• 0 <= nums[i] <= 100

链接：

https://leetcode-cn.com/problems/burst-balloons

题目分析

  观察示例可以发现，戳破气球可以让原本不相邻的气球变得相邻，如果每次戳破气球就按照实际情况移动数组肯定会导致复杂度过高，并且也不利于处理。最后必须要戳破所有的气球，那么我们可以考虑倒推。也即按照实际“戳破”相反的顺序，往数组中“添加”气球。
  由于数组边界视为有一个数值为 1 的气球，我们先把这两个边界加上存入一个新数组，便于后续的处理。对于区间 [i, j] 中添加气球会发生什么呢？假设 i 和 j 位置已经存在气球，并且开区间 (i, j) 中没有任何气球，那么我们往这个区间的位置 k 添加气球，获得的硬币数就是 nums[i] * nums[k] * nums[j]，并且这个时候问题转化成了往 (i, k) 和 (k, j) 中添加气球。基于这个思路我们就可以使用动态规划进行求解了。我们令 dp[i][j] 为填满 (i, j) 获得最多的硬币数。边界条件就是 (i, j) 中间已经没有数字。我们有这样的状态转移方程：

  注意动态规划的顺序，dp[i][j] 中 i 需要从大到小，而 j 则是从小到大，注意好需要计算的边界，其他的使用初始值 0 即可。而我们最后的答案就是 dp[0][n+1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n+2, vector<int>(n+2, 0));
        vector<int> newnums(n+2);
        newnums[0] = newnums[n+1] = 1;
        for(int i = 0; i < n; i++){
            newnums[i+1] = nums[i];
        }
        for(int i = n - 1; i >= 0; i--){
            for(int j = i + 2; j <= n + 1; j++){
                for(int k = i + 1; k < j; k++){
                    int sum = newnums[i] * newnums[k] * newnums[j];
                    sum += dp[i][k] + dp[k][j];
                    dp[i][j] = max(dp[i][j], sum);
                }
            }
        }
        return dp[0][n+1];
    }
};

  时间复杂度：$O(n^3)$，其中 $n$ 是数组的大小。我们一共有 $O(n^2)$ 种状态，而每一次状态转移的时间复杂度是 $O(n)$，因此总的时间复杂度为 $O(n*n^2)=O(n^3)$。
  空间复杂度：$O(n^2)$，其中 $n$ 是数组的大小。我们使用了一个 $O(n)$ 的数组作为新数组，并且使用一个 $O(n^2)$ 的数组记录状态，因此总的空间复杂度为 $O(n+n^2)=O(n^2)$。